// https://leetcode.cn/problems/container-with-most-water/

// 题干:给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
//      找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//      返回容器可以储存的最大水量。

// 示例:输入：[1,8,6,2,5,4,8,3,7]
//      输出：49

// 碎语:首先想到的是暴力解法，很多情况下，我们可以先顺着第一感觉，慢慢优化
//      因为vol=(right-left)*min(height[right],height[left])
//      所以固定一个柱子，另一个柱子往内移动，其成水量必定减少，故不必考虑
//      证明:width=right-left减少,min(height[right],height[left])不变或更小
//      综上，采用对撞指针，当两者相遇时候体积不存在，故循环停止

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int maxArea(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int ret = 0, vol = 0;

        while (left != right) {
            vol = (right - left) * min(height[left], height[right]);
            ret = max(ret, vol);

            if (height[left] < height[right]) left++;
            else right--;
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> height = {1,8,6,2,5,4,8,3,7};

    cout << sol.maxArea(height) << endl;

    return 0;
}